#ifndef _COMPLEX_LIST_
#define _COMPLEX_LIST_

#include <map>

// Definition for a Node.
class Node {
public:
    int   val;
    Node* next;
    Node* random;

    Node( int _val ) {
        val    = _val;
        next   = nullptr;
        random = nullptr;
    }
};

class ComplexList {
public:
    // my solution
    Node* copyRandomList( Node* head ) {
        // map key2value
        if ( head == nullptr ) {
            return nullptr;
        }

        std::map< Node*, Node* > address;

        Node* newHead = new Node( head->val );

        address.insert( std::map< Node*, Node* >::value_type( head, newHead ) );

        Node* oldtemp = head->next;
        Node* newtemp = newHead;
        Node* newNode;
        while ( oldtemp != nullptr ) {
            newNode = new Node( oldtemp->val );
            // for next
            newtemp->next = newNode;
            newtemp       = newNode;
            // for temp
            address.insert( std::map< Node*, Node* >::value_type( oldtemp, newtemp ) );
            // loop
            oldtemp = oldtemp->next;
        }

        oldtemp = head;
        while ( oldtemp != nullptr ) {
            if ( oldtemp->random != nullptr ) {
                newtemp         = address[ oldtemp ];
                newtemp->random = address[ oldtemp->random ];
            }

            oldtemp = oldtemp->next;
        }
        return newHead;
    }

    std::map< Node*, Node* > hashtable;

    // back + hash table
    Node* copyRandomList2( Node* head ) {
        if ( head == nullptr ) {
            return nullptr;
        }
        // if the key of head not present
        if ( !hashtable.count( head ) ) {
            Node* newHead     = new Node( head->val );
            hashtable[ head ] = newHead;
            newHead->next     = copyRandomList2( head->next );
            newHead->random   = copyRandomList2( head->random );
        }
        return hashtable[ head ];
    }

    // back + split (best)
    Node* copyRandomList3( Node* head ) {
        if ( head == nullptr ) {
            return nullptr;
        }
        Node* newNode;
        /*
        A->B->C
        A->A'->B->B'->C->C'
        */
        // for next point
        for ( Node* temp = head; temp != nullptr; temp = temp->next->next ) {
            newNode       = new Node( temp->val );
            newNode->next = temp->next;
            temp->next    = newNode;
        }
        // for random point
        for ( Node* temp = head; temp != nullptr; temp = temp->next->next ) {
            newNode         = temp->next;
            newNode->random = ( temp->random == nullptr ? nullptr : temp->random->next );
        }
        Node* newHead = head->next;
        // deep copy
        for ( Node* temp = head; temp != nullptr; temp = temp->next ) {
            newNode       = temp->next;
            temp->next    = temp->next->next;
            newNode->next = ( newNode->next == nullptr ? nullptr : temp->next->next );
        }

        return newHead;
    }
};

#endif /*_COMPLEX_LIST_*/